package top100;

import java.util.HashMap;
import java.util.Map;

/**
 * @see <a href="https://leetcode.cn/problems/two-sum/submissions/515372421/">twoSum</a>
 */
public class _01_twoSum {
    public static void main(String[] args) {

    }

    /**
     * 哈希表：
     *  创建一个哈希表，对于每一个 x，
     *  我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
     *
     * 时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
     * 空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> cache = new HashMap<Integer, Integer>();

        for(int i = 0; i<nums.length; i++) {
            int sub = target - nums[i];
            if (cache.get(sub) == null) {
                cache.put(nums[i], i);
            } else {
                return new int[] {cache.get(sub), i};
            }
        }

        return new int[0];
    }
}

